One way to frame the machine translation problem is to formulate it as
noisy-channel problem.  Where the most likely source (in our case
English) is the source sentence with the highest probability defined
by the product of a translation model and language model.

\begin{equation}
  \label{eq:noisy-channel-argmax}
  \mathbf{e} = \arg\max_{\mathbf{e}} P(\mathbf{f}|\mathbf{e}) P(\mathbf{e})
\end{equation}

In this paper we focus on the translation model
($P(\mathbf{f}|\mathbf{e})$) defined by IBM Model 4 (TODO:Cite).  IBM
Model 4 models the translation process as a generative story of how a
sequence of target words (in our case French or German) is generated
from a sequence of source words (English).  We briefly recap the
model.

We first being by describing the setup.  $\mathbf{e} = e_1, \dots,
e_l$ and $e_o$ is the NULL word.  $\mathbf{f} = f_1, \dots, f_m$.
%TODO: START and END tokens?

The generative story is as follows.  First, for each English token
$e_i$ we draw a fertility $\phi_i$ from a probability distribution
$n(\phi_i|e_i)$.  The fertility determines the number of french words
$e_i$ will generate.  A word with zero fertility is said to be
infertile, while words with non-zero fertility are fertile.  We then
generate the fertility for $e_0$ (the English NULL token) which will
be used to translate French tokens in the target not generated by
English tokens.

For each fertile element in the English sentence (including NULL) we
independently draw a sequence of French words
$(\tau_{ik})_{k=1\ldots\phi_i}$ for each English token $e_i$ according
to a translation table $t(\tau_{ik}|e_i)$.

Finally we process the English source tokens in sequence to determine
the positions of their generated French target words.  For each
fertile English token $e_i$ we randomly order all translations of
$e_i$ into a sequence.  The leftmost French word (called the
\emph{head}) of this sequence is placed at position $j$ based on the
averaged (and rounded) position $c_{\rho_{i}}$ of the translations of
the last previous fertile word $\rho_{i}$.  The distance
$j-c_{\rho_{i}}$ is picked according to the distribution
$d_{1}(j-c_{\rho_{i}}|\mathit{class}(e_{\rho_{i}}),\mathit{class}(f_{j}))$
which is conditioned on the word classes of the previous fertile
English word and the French head word.

For words other than the leftmost (i.e. non-head words) the position
$k$ is determined with respect to the position of the head word $j$
according to a distribution $d_{>1}(k-j|class(f_k))$.

Finally, the positions of all NULL-generated words are distributed
to the remaining slots uniformly.

\begin{eqnarray*}
 & p\left(a,f|e\right)=\\
 & \prod_{i=1}^{l}n\left(\phi_{i}|e_{i}\right)\times\prod_{i=1}^{l}\prod_{k=1}^{\phi_{i}}t\left(\tau_{ik},e_{i}\right)\times\\
 & \prod_{i=1,\phi_{i}>0}^{l}d_{1}\left(\pi_{i1}-c_{\rho_{i}}|class\left(e_{\rho_{i}}\right),class\left(\tau_{i1}\right)\right)\times\\
 & \prod_{i=1}^{l}\prod_{k=2}^{\phi_{i}}d_{>1}\left(\pi_{ik}-\pi_{i\left(k-1\right)}|class\left(\tau_{ik}\right)\right)\times\\
 & \left(\begin{array}{c}
m-\phi_{0}\\
\phi_{0}\end{array}\right)p_{1}^{\phi_{0}}\left(1-p_{1}\right)^{m-2\phi_{0}}\times\\
 & \prod_{k=1}^{\phi_{0}}t\left(\tau_{0k}|\text{NULL}\right)\end{eqnarray*}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ilp-mt"
%%% End: 
